{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Flowers in Full Bloom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #binary-search #ordered-set #prefix-sum #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #二分查找 #有序集合 #前缀和 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fullBloomFlowers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #花期内花的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的二维整数数组&nbsp;<code>flowers</code>&nbsp;，其中&nbsp;<code>flowers[i] = [start<sub>i</sub>, end<sub>i</sub>]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;朵花的 <strong>花期</strong>&nbsp;从&nbsp;<code>start<sub>i</sub></code>&nbsp;到&nbsp;<code>end<sub>i</sub></code>&nbsp;（都 <strong>包含</strong>）。同时给你一个下标从 <strong>0</strong>&nbsp;开始大小为 <code>n</code>&nbsp;的整数数组&nbsp;<code>people</code> ，<code>people[i]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;个人来看花的时间。</p>\n",
    "\n",
    "<p>请你返回一个大小为 <code>n</code>&nbsp;的整数数组<em>&nbsp;</em><code>answer</code>&nbsp;，其中&nbsp;<code>answer[i]</code>是第&nbsp;<code>i</code>&nbsp;个人到达时在花期内花的&nbsp;<strong>数目</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/02/ex1new.jpg\" style=\"width: 550px; height: 216px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]\n",
    "<b>输出：</b>[1,2,2,2]\n",
    "<strong>解释：</strong>上图展示了每朵花的花期时间，和每个人的到达时间。\n",
    "对每个人，我们返回他们到达时在花期内花的数目。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/02/ex2new.jpg\" style=\"width: 450px; height: 195px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>flowers = [[1,10],[3,3]], people = [3,3,2]\n",
    "<b>输出：</b>[2,2,1]\n",
    "<b>解释：</b>上图展示了每朵花的花期时间，和每个人的到达时间。\n",
    "对每个人，我们返回他们到达时在花期内花的数目。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= flowers.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>flowers[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= start<sub>i</sub> &lt;= end<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= people.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= people[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-flowers-in-full-bloom](https://leetcode.cn/problems/number-of-flowers-in-full-bloom/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-flowers-in-full-bloom](https://leetcode.cn/problems/number-of-flowers-in-full-bloom/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,6],[3,7],[9,12],[4,13]]\\n[2,3,7,11]', '[[1,10],[3,3]]\\n[3,3,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        starts = []\n",
    "        ends = []\n",
    "        for start, end in flowers:\n",
    "            starts.append(start)\n",
    "            ends.append(end)\n",
    "        starts.sort()\n",
    "        ends.sort()\n",
    "    \n",
    "        peopleSorted = sorted(people)\n",
    "        ans = {}\n",
    "        startIdx = 0\n",
    "        endIdx = 0\n",
    "        blooms = 0\n",
    "        for p in peopleSorted:\n",
    "            while startIdx < len(starts) and starts[startIdx] <= p:\n",
    "                blooms += 1\n",
    "                startIdx += 1\n",
    "            while endIdx < len(ends) and ends[endIdx] < p:\n",
    "                blooms -= 1\n",
    "                endIdx += 1\n",
    "            ans[p] = blooms\n",
    "            \n",
    "        return [ans[p] for p in people]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:\n",
    "        flowers.sort(key=lambda x: -x[0])\n",
    "        from sortedcontainers import SortedList\n",
    "        q = SortedList()\n",
    "        ans = {}\n",
    "        for p in sorted(persons):\n",
    "            while flowers and flowers[-1][0] <= p:\n",
    "                q.add(flowers.pop()[1])\n",
    "            while q and q[0] < p:\n",
    "                q.pop(0)\n",
    "            ans[p] = len(q)\n",
    "        return [ans[p] for p in persons]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import * \n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:\n",
    "        \n",
    "        heapify(flowers)\n",
    "        heap = []\n",
    "        persons = sorted(enumerate(persons), key = lambda x : x[1])\n",
    "        n = len(persons)\n",
    "        answer = [0] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            j, t = persons[i]\n",
    "            while flowers and flowers[0][0] <= t:\n",
    "                heappush(heap, heappop(flowers)[1])\n",
    "            while heap and heap[0] < t:\n",
    "                heappop(heap)\n",
    "            answer[j] = len(heap)\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:\n",
    "        \n",
    "        start, end = [x for x,y in flowers], [y for x,y in flowers]\n",
    "        start, end  = sorted(start), sorted(end)\n",
    "        #print(start,end)\n",
    "        l_person, l_flower = len(persons), len(flowers)\n",
    "        idx = sorted(range(l_person), key=lambda k: persons[k])\n",
    "        count = 0\n",
    "        a,b = 0,0\n",
    "        ret = [0 for _ in range(l_person)]\n",
    "        for i in idx:\n",
    "            time = persons[i]\n",
    "            while a<l_flower and start[a]<=time:\n",
    "                count += 1\n",
    "                a += 1\n",
    "            while b<l_flower and end[b]<time:\n",
    "                count -= 1\n",
    "                b += 1\n",
    "            #print(a,b,count)\n",
    "            ret[i] = count\n",
    "            \n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:\n",
    "        d = defaultdict(int)\n",
    "        d[0] = 0\n",
    "        for st, ed in flowers:\n",
    "            d[st] += 1\n",
    "            d[ed+1] -= 1\n",
    "        ks = list(sorted(d.keys()))\n",
    "        for i, k in enumerate(ks):\n",
    "            if i > 0: d[k] += d[ks[i-1]]\n",
    "        res = [0] * len(persons)\n",
    "        for i, p in enumerate(persons):\n",
    "            j = bisect_left(ks, p+1) - 1\n",
    "            res[i] = d[ks[j]]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        query = sorted(people)\n",
    "        flowers.sort(reverse=True)\n",
    "        heap = []\n",
    "        cnt = 0\n",
    "        dic = {}\n",
    "        for p in query:\n",
    "            if p in dic:\n",
    "                continue\n",
    "            while flowers and flowers[-1][0] <= p:\n",
    "                f = flowers.pop()\n",
    "                heapq.heappush(heap, f[1])\n",
    "                cnt += 1\n",
    "            while heap and heap[0] < p:\n",
    "                heapq.heappop(heap)\n",
    "                cnt -= 1\n",
    "            dic[p] = cnt\n",
    "        return [dic[p] for p in people]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:\n",
    "        heap, peopleList, dic, pres = [], sorted(persons), {}, 0\n",
    "        flowers.sort()\n",
    "        for x in peopleList:\n",
    "            while pres < len(flowers) and flowers[pres][0] <= x:\n",
    "                heappush(heap, flowers[pres][1])\n",
    "                pres += 1\n",
    "            while heap and heap[0] < x:\n",
    "                heappop(heap)\n",
    "            dic[x] = len(heap)\n",
    "        return [dic[x] for x in persons]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        visit = {t:0 for t in people}\n",
    "        heap = []\n",
    "        heapify(flowers)\n",
    "        for t in sorted(visit.keys()):\n",
    "            while flowers and flowers[0][0] <= t:\n",
    "                heappush(heap, flowers[0][-1])\n",
    "                heappop(flowers)\n",
    "            while heap and heap[0] < t:\n",
    "                heappop(heap)\n",
    "            visit[t] = len(heap)\n",
    "        return [visit[t] for t in people]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "      flowerSeq = dict()\n",
    "      for start, end in flowers:\n",
    "        flowerSeq[start] = flowerSeq.get(start, 0) + 1\n",
    "        flowerSeq[end+1] = flowerSeq.get(end+1, 0) - 1\n",
    "        if flowerSeq[start] == 0:\n",
    "          del flowerSeq[start]\n",
    "        if flowerSeq[end+1] == 0:\n",
    "          del flowerSeq[end+1]\n",
    "        \n",
    "      timeSeq = sorted(flowerSeq)\n",
    "      n = len(timeSeq)\n",
    "      for i in range(1, n):\n",
    "        flowerSeq[timeSeq[i]] += flowerSeq[timeSeq[i-1]]\n",
    "      \n",
    "      for i in range(len(people)):\n",
    "        L, R = 0, n-1\n",
    "        while L <= R:\n",
    "          mid = (L + R) // 2\n",
    "          if timeSeq[mid] == people[i]:\n",
    "            L = mid + 1\n",
    "            break\n",
    "          elif timeSeq[mid] > people[i]:\n",
    "            R = mid - 1\n",
    "          else:\n",
    "            L = mid + 1\n",
    "        people[i] = flowerSeq[timeSeq[L-1]]\n",
    "      return people"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "      flowerSeq = dict()\n",
    "      for start, end in flowers:\n",
    "        flowerSeq[start] = flowerSeq.get(start, 0) + 1\n",
    "        flowerSeq[end+1] = flowerSeq.get(end+1, 0) - 1\n",
    "        if flowerSeq[start] == 0:\n",
    "          del flowerSeq[start]\n",
    "        if flowerSeq[end+1] == 0:\n",
    "          del flowerSeq[end+1]\n",
    "        \n",
    "      timeSeq = sorted(flowerSeq)\n",
    "      n = len(timeSeq)\n",
    "      for i in range(1, n):\n",
    "        flowerSeq[timeSeq[i]] += flowerSeq[timeSeq[i-1]]\n",
    "      \n",
    "      for i in range(len(people)):\n",
    "        L, R = 0, n-1\n",
    "        while L <= R:\n",
    "          mid = (L + R) // 2\n",
    "          if timeSeq[mid] == people[i]:\n",
    "            L = mid + 1\n",
    "            break\n",
    "          elif timeSeq[mid] > people[i]:\n",
    "            R = mid - 1\n",
    "          else:\n",
    "            L = mid + 1\n",
    "        people[i] = flowerSeq[timeSeq[L-1]]\n",
    "      return people"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        people = sorted(((j, i) for i, j in enumerate(people)), key=lambda x: x[0])\n",
    "        flowers.sort(key=lambda x: -x[0])\n",
    "        n = len(people)\n",
    "        ans = [0] * n\n",
    "        h = []\n",
    "        for i, idx in people:\n",
    "            while flowers and flowers[-1][0] <= i:\n",
    "                s,e = flowers.pop()\n",
    "                heappush(h, e)\n",
    "            while h and h[0] < i:\n",
    "                heappop(h)\n",
    "            ans[idx] = len(h)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        diff = Counter()\n",
    "        for start, end in flowers:\n",
    "            diff[start] += 1\n",
    "            diff[end + 1] -= 1\n",
    "        times = sorted(diff.keys())\n",
    "\n",
    "        j = s = 0\n",
    "        for p, i in sorted(zip(people, range(len(people)))):\n",
    "            while j < len(times) and times[j] <= p:\n",
    "                s += diff[times[j]]  # 累加不超过 people[i] 的差分值\n",
    "                j += 1\n",
    "            people[i] = s  # 从而得到这个时刻花的数量\n",
    "        return people\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "\n",
    "        diff = Counter()\n",
    "        for s, e in flowers:\n",
    "            diff[s] += 1\n",
    "            diff[e + 1] -= 1\n",
    "        n = len(people)\n",
    "        keys = sorted(diff.keys())\n",
    "        pres = j = 0\n",
    "        ans = [0] * n\n",
    "        for i, p in sorted(zip(range(n), people), key=lambda x: x[1]):\n",
    "\n",
    "            while j < len(keys) and keys[j] <= p:\n",
    "                pres += diff[keys[j]]\n",
    "                j += 1\n",
    "            ans[i] = pres\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        starts = sorted(start for start, _ in flowers)\n",
    "        ends = sorted(end for _, end in flowers)\n",
    "        answer = [bisect.bisect_right(starts, p) - bisect.bisect_left(ends, p) for p in people]\n",
    "        return answer\n",
    "\n",
    "\n",
    "        diff = collections.Counter()\n",
    "        for start, end in flowers:\n",
    "            diff[start] += 1\n",
    "            diff[end + 1] -= 1\n",
    "        n = len(people)\n",
    "        ans = [0] * n\n",
    "        nums = 0\n",
    "        d = sorted(diff.keys())\n",
    "        i = 0\n",
    "        m = len(d)\n",
    "        for x, p in sorted(zip(people, range(n))):\n",
    "            while i < m and d[i] <= x:\n",
    "                nums += diff[d[i]]\n",
    "                i += 1\n",
    "            ans[p] = nums\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        length = len(flowers)\n",
    "        f_open = sorted(x[0] for x in flowers)\n",
    "        f_close = sorted(x[1] for x in flowers)\n",
    "        \n",
    "        res = [bisect.bisect_right(f_open, x) - bisect.bisect_left(f_close, x) for x in people]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        length = len(flowers)\n",
    "        f_open = sorted(x[0] for x in flowers)\n",
    "        f_close = sorted(x[1] for x in flowers)\n",
    "\n",
    "        def check_open(val):\n",
    "            l, r = 0, length\n",
    "            while l < r:\n",
    "                m = l + (r-l) // 2\n",
    "                if f_open[m] <= val:\n",
    "                    l = m + 1\n",
    "                else: \n",
    "                    r = m\n",
    "            return l\n",
    "\n",
    "        def check_close(val):\n",
    "            l, r = 0, length\n",
    "            while l < r:\n",
    "                m = l + (r-l) // 2\n",
    "                if f_close[m] < val:\n",
    "                    l = m + 1\n",
    "                else: \n",
    "                    r = m\n",
    "            return l\n",
    "        \n",
    "        res = [check_open(x) - check_close(x) for x in people]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        starts = sorted([start for start, _ in flowers])\n",
    "        ends = sorted([end for _, end in flowers])\n",
    "        return [bisect_right(starts, p) - bisect_left(ends, p) for p in people]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        s = [s for s, e in flowers]\n",
    "        e = [e for s, e in flowers]\n",
    "        n = len(flowers)\n",
    "        s.sort()\n",
    "        e.sort()\n",
    "        p1, p2 = 0, 0\n",
    "        ans = [0]*len(people)\n",
    "        people = sorted([[j, i] for i, j in list(enumerate(people))])\n",
    "        for ppl, i in people:\n",
    "            while p1<n and s[p1]<= ppl:\n",
    "                p1 += 1\n",
    "            while p2<n and e[p2]< ppl:\n",
    "                p2 += 1\n",
    "            ans[i] = p1 - p2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        flower_num = Counter()\n",
    "        for f in flowers:\n",
    "            s, e = f \n",
    "            flower_num[s]+=1\n",
    "            flower_num[e+1]-=1\n",
    "        flower_num = sorted(flower_num.items(), key = lambda x: x[0])\n",
    "        print(flower_num)\n",
    "        people = [(p, i) for i,p in enumerate(people)]\n",
    "        people.sort()\n",
    "        i = 0\n",
    "        ans = [0]*len(people)\n",
    "        prev = 0\n",
    "        for p,id in people:\n",
    "            while i<len(flower_num) and flower_num[i][0]<=p:\n",
    "                prev+=flower_num[i][1] \n",
    "                i+=1\n",
    "            ans[id] = prev\n",
    "        return ans\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "\n",
    "        # 拆出开花时间，和凋谢时间\n",
    "        starts = SortedList()\n",
    "        ends = SortedList()\n",
    "\n",
    "        for start, end in flowers:\n",
    "            starts.add(start)\n",
    "            ends.add(end)\n",
    "        \n",
    "        ans = []\n",
    "        for peo in people:\n",
    "            # 在开花中找到第一个大于的开花\n",
    "            # 在凋零中找到第一个大于等于的凋零\n",
    "            start_pos = starts.bisect_right(peo)\n",
    "            end_pos = ends.bisect_left(peo)\n",
    "            ans.append(start_pos-end_pos)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        cnt = collections.defaultdict(int)\n",
    "        for start, end in flowers:\n",
    "            cnt[start] += 1\n",
    "            cnt[end + 1] -= 1\n",
    "            # print(cnt)\n",
    "        flower_times = sorted(cnt.items())\n",
    "        # print(flower_times)\n",
    "\n",
    "        n = len(people)\n",
    "        ans = [0 for _ in range(n)]\n",
    "        f_pointer, current = 0, 0\n",
    "        for visit_time, pi in sorted(zip(people, range(n))):\n",
    "            # print(f\"current: {current}, f_p: {f_pointer}, pidx: {pi}\")\n",
    "            while f_pointer < len(flower_times) and flower_times[f_pointer][0] <= visit_time:\n",
    "                current += flower_times[f_pointer][1]\n",
    "                f_pointer += 1\n",
    "            # print(f\"current: {current}, f_p: {f_pointer}, pidx: {pi}\")\n",
    "            ans[pi] = current\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        length = len(flowers)\n",
    "        f_open = sorted(x[0] for x in flowers)\n",
    "        f_close = sorted(x[1] for x in flowers)\n",
    "\n",
    "        @cache\n",
    "        def check_open(val):\n",
    "            l, r = 0, length\n",
    "            while l < r:\n",
    "                m = l + (r-l) // 2\n",
    "                if f_open[m] <= val:\n",
    "                    l = m + 1\n",
    "                else: \n",
    "                    r = m\n",
    "            return l\n",
    "\n",
    "        @cache\n",
    "        def check_close(val):\n",
    "            l, r = 0, length\n",
    "            while l < r:\n",
    "                m = l + (r-l) // 2\n",
    "                if f_close[m] < val:\n",
    "                    l = m + 1\n",
    "                else: \n",
    "                    r = m\n",
    "            return l\n",
    "        \n",
    "        #cache_clear()\n",
    "        res = [check_open(x) - check_close(x) for x in people]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        a = []\n",
    "        m = len(flowers) * 2\n",
    "        for x in flowers:\n",
    "            a.append([x[0], 1])\n",
    "            a.append([x[1] + 1, -1])\n",
    "        a.sort(key = lambda x: x[0])\n",
    "        \n",
    "        b = []\n",
    "        n = len(people)\n",
    "        for i in range(n):\n",
    "            b.append([people[i], i])\n",
    "        b.sort(key = lambda x: x[0])\n",
    "        now = 0\n",
    "        cnt = 0\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            while now < m and a[now][0] <= b[i][0]:\n",
    "                cnt += a[now][1]\n",
    "                now += 1\n",
    "            ans[b[i][1]] = cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        n = len(people)\n",
    "        pq = []\n",
    "\n",
    "        # prority: 0-bloom 1-people arrive 2-die \n",
    "        for i in range(n):\n",
    "            #[people arriving time, 1, i]\n",
    "            heapq.heappush(pq, [people[i], 1, i])\n",
    "        \n",
    "        for flower in flowers:\n",
    "            #bloom-[time, 0]\n",
    "            heapq.heappush(pq, [flower[0], 0])\n",
    "            #die-[time, 2]\n",
    "            heapq.heappush(pq, [flower[1], 2])\n",
    "\n",
    "\n",
    "        res = [0] * n \n",
    "        bloom = 0\n",
    "        while pq:\n",
    "            tmp = heapq.heappop(pq)\n",
    "            if tmp[1] == 0:\n",
    "                bloom += 1 \n",
    "\n",
    "            elif tmp[1] == 1:\n",
    "                idx = tmp[2]\n",
    "                res[idx] = bloom\n",
    "            elif tmp[1] == 2:\n",
    "                bloom -= 1 \n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "\n",
    "        from collections import defaultdict\n",
    "        dic = defaultdict(int)\n",
    "        for start, end in flowers:\n",
    "            dic[start] += 1\n",
    "            dic[end + 1] -= 1\n",
    "\n",
    "        nums = list(dic.keys())\n",
    "        nums.sort()\n",
    "\n",
    "        seq = []\n",
    "        s = 0\n",
    "        for k in nums:\n",
    "            s += dic[k]\n",
    "            seq.append((k, s))\n",
    "\n",
    "        people = [(i, p) for i, p in enumerate(people)]\n",
    "        people.sort(key=lambda x: x[1])\n",
    "\n",
    "        def binary_search(nums, target):\n",
    "            lo, hi = 0, len(nums)\n",
    "            while lo < hi:\n",
    "                mid = lo + (hi - lo) // 2\n",
    "                if nums[mid][0] <= target:\n",
    "                    lo = mid + 1\n",
    "                else:\n",
    "                    hi = mid\n",
    "            return lo - 1\n",
    "\n",
    "        ans = [0] * len(people)\n",
    "        for i, t in people:\n",
    "            index = binary_search(seq, t)\n",
    "            ans[i] = seq[index][1]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:\n",
    "        a, c = [], Counter()\n",
    "        for s, e in flowers:\n",
    "            a.append([s, 1])\n",
    "            a.append([e + 1, -1])\n",
    "        for p in people:\n",
    "            a.append([p, 2])\n",
    "        a.sort()\n",
    "        n = 0\n",
    "        for a, b in a:\n",
    "            if b < 2:\n",
    "                n += b\n",
    "            else:\n",
    "                c[a] = n\n",
    "        return [c[i] for i in people]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
